package com.cuz.二叉树;

import java.util.Stack;
import java.util.concurrent.atomic.AtomicLong;

public class l98验证二叉搜索树 {
    public static void main(String[] args) {
        //[5,1,4,null,null,3,6]
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        TreeNode node4 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);

        node5.left = node1;
        node5.right = node4;
        node4.left = node3;
        node6.right = node6;

        //2,1,3
        TreeNode node22 = new TreeNode(2);
        TreeNode node21 = new TreeNode(1);
        TreeNode node23 = new TreeNode(3);
        node22.left = node21;
        node22.right = node23;
        Info process = new l98验证二叉搜索树().process(node5);

        System.out.println(process.isBst);
    }

    static class Info {
        Integer min;
        Integer max;
        boolean isBst;

        Info(Integer min, Integer max, boolean flag) {
            this.min = min;
            this.max = max;
            this.isBst = flag;
        }
    }

    private Info process(TreeNode node) {
        if (node == null) {
            return null;
        }

        boolean isBst = true;

        //左树最大，右树最小 二者是否bst
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        if (leftInfo != null) {
            isBst = leftInfo.isBst;
        }
        if (rightInfo != null) {
            isBst = isBst && rightInfo.isBst;
        }
        if (!isBst){
            return new Info(null,null,isBst);
        }
        //左右是bst
        //左边最大 是否小于当前节点
        if (leftInfo!=null && leftInfo.max >= node.val){
            isBst = false;
        }
        //右边最小 是否小于当前节点
        if (rightInfo!=null && rightInfo.min <= node.val){
            isBst = false;
        }
        if (!isBst){
            return new Info(null,null,isBst);
        }
        //说明是bst

        Integer min  = node.val;
        Integer max  = node.val;
        if (leftInfo!=null){
            min = leftInfo.min;
        }
        if (rightInfo!=null){
            max = rightInfo.max;
        }
        return new Info(min, max, true);
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        return check(root, new AtomicLong(Long.MIN_VALUE));
    }


    private boolean check(TreeNode node, AtomicLong preValue) {
        if (node == null) {
            return true;
        }

        boolean isLeftBST = check(node.left, preValue);

        if (!isLeftBST) {
            return false;
        }
        if (node.val > preValue.get()) {
            preValue.set(node.val);
        } else {
            return false;
        }

        return check(node.right, preValue);
    }

    private boolean check(TreeNode root) {
        if (root == null) {
            return true;
        }
        Integer pre = null;
        Stack<TreeNode> stack = new Stack<>();
        do {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                if (pre == null || pre < root.val) {
                    pre = root.val;
                } else {
                    return false;
                }
                root = root.right;
            }
        } while (!stack.isEmpty() || root != null);

        return true;
    }


}
